package c01_array;

import java.util.*;

/**
 * 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
 *
 * 满足要求的四元组集合为：
 * [
 *   [-1,  0, 0, 1],
 *   [-2, -1, 1, 2],
 *   [-2,  0, 0, 2]
 * ]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/4sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class S18 {
    public static void main(String[] args) {
        int[] nums = new int[] {1, 0, -1, 0, -2, 2};

        int target= 0;
        S18 s18 = new S18();
        List<List<Integer>> lists = s18.fourSum(nums, target);
        System.out.println(lists);

    }
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums==null) {
            return Collections.EMPTY_LIST;
        }
        if(nums.length<4) {
            return Collections.EMPTY_LIST;
        }
        Arrays.sort(nums);
        Set<List<Integer>> set = new HashSet<>();
        int minSum = nums[0]+nums[1]+nums[2]+nums[3];
        int maxSum = nums[nums.length-1]+nums[nums.length-2]+nums[nums.length-3]+nums[nums.length-4];
        if (target>maxSum) {
            return Collections.EMPTY_LIST;
        }else if(target<minSum){
            return Collections.EMPTY_LIST;
        }
        //sum: [int1,int2] in order
        Map<Integer,List<List<Integer>>> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j <nums.length ; j++) {
                int sum = nums[i]+nums[j];
                map.computeIfAbsent(sum,(key)-> new ArrayList<>(2));
                map.get(sum).add(Arrays.asList(nums[i],nums[j]));
            }
        }
        for (int i = 0; i < nums.length; i++) {
            int iNum = nums[i];
            for (int j = i+1; j <nums.length ; j++) {
                int jNum = nums[j];
                int sum = iNum+jNum;
                int targetNum = target-sum;
                if(!map.containsKey(targetNum)) {
                    continue;
                }else {
                    List<List<Integer>> lists = map.get(targetNum);
                    for (List<Integer> list : lists) {
                        //因为是有序的, 所以如果第三个数小于第二个数据不要了
                        if(list.get(0)<jNum) {
                            continue;
                        } else {
                            List<Integer> integers = Arrays.asList(iNum, jNum, list.get(0), list.get(1));
                            if(containAllElements(nums,integers)) {
                                set.add(integers);
                            }
                        }
                    }
                }
            }
        }
        return new ArrayList<>(set);
    }
    //处理相同元素
    public boolean containAllElements(int[] arr, List<Integer> list) {
        int patchNum =0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]==list.get(patchNum)) {
                patchNum++;
                if(patchNum>=4) {
                    return true;
                }
            }
            if(arr[i]>list.get(3)) {
                return false;
            }
        }
        return false;
    }
}
